package lc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q401 {

    public static void main(String[] args) {
        Q401 q401 = new Q401();
        List<int[]> merge = q401.merge(new ArrayList<>(
                Arrays.asList(new int[]{1, 4, 1}, new int[]{6, 8, 1})
        ), new int[]{0, 2, 2});
        for (int[] ints : merge) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public List<int[]> merge(List<int[]> prev, int[] current) {
        // prev区间无交集，只有并集情况（即前一个点的右边等于后一个点的左边）
        int start = current[0];
        int end = current[1];
        int num = current[2];
        // 遍历prev，获取要分割的点，如果start在prev任何元素前，如果start在prev任何元素之后，
        // 那么再prev后加上  prev[last][1] -> start
        int startI = -1;
        for (int i = 0; i <= prev.size(); i++) {
            if (i == prev.size()) {
                startI ++;
                break;
            }
            int[] ints = prev.get(i);
            if (start >= ints[0] && start <= ints[1]) {
                startI = i;
                break;
            } else if (start < ints[0]) {
                // 停止查找
                break;
            }else {
                // 避免都找不到所以
                startI ++;
            }
        }
        if (startI == prev.size()) {
            // 那么直接在最后拼上值就行
            ArrayList<int[]> result = new ArrayList<>(prev);
            result.add(current);
            return result;
        }
        // 继续找end分割点
        int endI = prev.size();
        for (int i = prev.size() - 1; i >= -1; i--) {
            if (i == -1) {
                endI ++;
                break;
            }
            int[] ints = prev.get(i);
            if (end >= ints[0] && end <= ints[1]) {
                endI = i;
                break;
            } else if (end > ints[1]) {
                // 如果右边界比所有的右边界大
                break;
            }else {
                // 避免都找不到所以
                endI --;
            }
        }
        // 如果endI等于-1，那么
        if (endI == -1) {
            ArrayList<int[]> result = new ArrayList<>();
            result.add(current);
            result.addAll(prev);
            return result;
        }

        // 开始分割了，总共最多五部分，小于start，，大于end
        ArrayList<int[]> result = new ArrayList<>();

        for (int i = 0; i < startI; i++) {
            result.add(prev.get(i));
        }
        // 超出边界情况没处理，如startI是-1，endI是size情况
        // start到end之间，所有的区间需要拆分成startI[0] -> start,start->startI[1], (startI)[1] ->(startI+1)[0] startI+2 ... endI -> end end -> endI[1]
        if (startI == -1) {
            // 将值拼到前面
            result.add(new int[]{start, prev.get(0)[0], num});
            // startI设置成0
            startI = 0;
        }
        int[] si = prev.get(startI);
        if (si[0] < start) {
            result.add(new int[]{si[0], start, si[2]});
        }
        int[] pv = si;
        for (int i = startI + 1; i <= Integer.min(endI, prev.size() - 1); i++) {
            if (result.get(result.size() - 1)[1] < pv[1]) {
                result.add(new int[]{result.get(result.size() - 1)[1], pv[1], pv[2] + num});
            }
            pv = prev.get(i);
            if (result.get(result.size() - 1)[1] < pv[0]) {
                result.add(new int[]{result.get(result.size() - 1)[1], pv[0], num});
            }
        }
        if (endI == prev.size()) {
            // 将值拼到后面
            result.add(new int[]{prev.get(endI - 1)[1], end, num});
        } else {
            int[] ei = prev.get(endI);
            // 此时pv到了最后了
            if (ei[0] < end) {
                result.add(new int[]{ei[0],end, ei[2] + num});
            }
            if (end < ei[1]) {
                result.add(new int[]{end,ei[1], ei[2]});
            }
        }

        for (int i = endI + 1; i < prev.size(); i++) {
            result.add(prev.get(i));
        }
        return result;
    }

}
